/*
Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].
*/

class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        slen = s.length();
        vector<bool> wordB(slen + 1, false);
        vector<vector<int> >wordP(slen + 1);
        wordB[0] = true;
        for (int i = 0; i < slen; i++) {
            for (int j = 0; j <= i; j++) {
                if (wordB[j] && dict.find(s.substr(j, i - j + 1)) != dict.end()) {
                    wordB[i+1] = true;
                    wordP[i+1].push_back(j);
                }
            }
        }
        vector<string> words;
        if (wordB[slen] == false) return words;
        string tmpword("");
        // back track to get all Combo words
        makeCombo(slen, s, tmpword, words, wordP);
        return words;
    }
private:
    int slen;
    void makeCombo(int end, string &s, string curword, vector<string> &words, vector<vector<int> >&wordP) {
        if (!end) { words.push_back(curword); return; }
        for (auto it = wordP[end].begin(); it != wordP[end].end(); it++) {
            int mid = *it;
            string newword("");
            if (!curword.length()) newword = s.substr(mid, end-mid); // last word
            else newword = s.substr(mid, end-mid) + " " + curword;
            makeCombo(mid, s, newword, words, wordP);
        }
    }
};
